<head>
    <meta charset="UTF-8">
<title>历届试题 格子刷油漆</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>&nbsp; &nbsp; X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。</div>
<div>&nbsp;</div>
<div><img src="http://lx.lanqiao.cn/RequireFile.do?fid=HLt96rLF" width="439" height="234" alt="" /></div>
<div>&nbsp; &nbsp; 你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）</div>
<div>&nbsp; &nbsp; 比如：a d b c e f 就是合格的刷漆顺序。</div>
<div>&nbsp; &nbsp; c e f d a b 是另一种合适的方案。</div>
<div>&nbsp; &nbsp; 当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。</div>
<p>【输入格式】</p>
<div>&nbsp; &nbsp; 输入数据为一个正整数（不大于1000）</div>
<p>【输出格式】</p>
<div>&nbsp; &nbsp; 输出数据为一个正整数。</div>
<p>【样例输入】</p>
<div>2</div>
<p>【样例输出】</p>
<div>24</div>
<div>
<div>【样例输入】<br />
<div>3</div>
<div>【样例输出】</div>
<div>96</div>
</div>
</div>
<div>【样例输入】<br />
<div>22</div>
<div>【样例输出】</div>
<div>
<div>359635897</div>
</div>
</div>
<div>&nbsp;</div>